{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hasPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "由空地（用 <code>0</code> 表示）和墙（用 <code>1</code> 表示）组成的迷宫 <code>maze</code> 中有一个球。球可以途经空地向<strong> 上、下、左、右 </strong>四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。\n",
    "<div class=\"top-view__1vxA\">\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>给你一个大小为 <code>m x n</code> 的迷宫 <code>maze</code> ，以及球的初始位置 <code>start</code> 和目的地 <code>destination</code> ，其中 <code>start = [start<sub>row</sub>, start<sub>col</sub>]</code> 且 <code>destination = [destination<sub>row</sub>, destination<sub>col</sub>]</code> 。请你判断球能否在目的地停下：如果可以，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>你可以 <strong>假定迷宫的边缘都是墙壁</strong>（参考示例）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg\" style=\"width: 573px; height: 573px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/31/maze1-2-grid.jpg\" style=\"width: 573px; height: 573px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == maze.length</code></li>\n",
    "\t<li><code>n == maze[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 100</code></li>\n",
    "\t<li><code>maze[i][j]</code> is <code>0</code> or <code>1</code>.</li>\n",
    "\t<li><code>start.length == 2</code></li>\n",
    "\t<li><code>destination.length == 2</code></li>\n",
    "\t<li><code>0 <= start<sub>row</sub>, destination<sub>row</sub> <= m</code></li>\n",
    "\t<li><code>0 <= start<sub>col</sub>, destination<sub>col</sub> <= n</code></li>\n",
    "\t<li>球和目的地都在空地上，且初始时它们不在同一位置</li>\n",
    "\t<li>迷宫 <strong>至少包括 2 块空地</strong></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-maze](https://leetcode.cn/problems/the-maze/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-maze](https://leetcode.cn/problems/the-maze/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]\\n[0,4]\\n[4,4]', '[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]\\n[0,4]\\n[3,2]', '[[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]]\\n[4,3]\\n[0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        stop = []\n",
    "        visited = set()\n",
    "        que = []\n",
    "        width = len(maze[0])\n",
    "        que.append(start)\n",
    "        \n",
    "        while que:\n",
    "            cur = que[0]\n",
    "            \n",
    "            if (cur[0] * width + cur[1]) in visited:\n",
    "                que.pop(0)\n",
    "                continue\n",
    "            # visited.append([cur[0],cur[1]])\n",
    "            visited.add(cur[0] * width + cur[1])\n",
    "            \n",
    "            #check left side\n",
    "            if cur[1]-1 >= 0 and maze[cur[0]][cur[1]-1] == 0:\n",
    "                temp = cur[1]\n",
    "                while temp >= 0 and maze[cur[0]][temp] == 0:\n",
    "                    temp -=1\n",
    "                temp += 1\n",
    "                cur_ = [cur[0],temp]\n",
    "                if (cur[0]*width + temp) not in visited:\n",
    "                    # visited.append(cur_)\n",
    "                    que.append([cur[0],temp])\n",
    "                stop.append([cur[0],temp])\n",
    "            #check right side:\n",
    "            if cur[1]+1 <len(maze[0]) and maze[cur[0]][cur[1]+1] == 0:\n",
    "                temp = cur[1]\n",
    "                while temp < len(maze[0]) and maze[cur[0]][temp] == 0:\n",
    "                    temp +=1\n",
    "                temp -= 1\n",
    "                if (cur[0]*width + temp)  not in visited:\n",
    "                    # visited.append(cur_)\n",
    "                    que.append([cur[0],temp])\n",
    "                stop.append([cur[0],temp])\n",
    "            #check up side\n",
    "            if cur[0] - 1 >= 0 and maze[cur[0]-1][cur[1]] == 0:\n",
    "                temp = cur[0]\n",
    "                while temp >= 0 and maze[temp][cur[1]] == 0:\n",
    "                    temp -=1\n",
    "                temp += 1\n",
    "                if (temp* width + cur[1]) not in visited:\n",
    "                    # visited.append(cur_)\n",
    "                    que.append([temp, cur[1]])\n",
    "                stop.append([temp,cur[1]])\n",
    "            #check down side\n",
    "            if cur[0] +1 < len(maze) and maze[cur[0]+1][cur[1]] == 0:\n",
    "                temp = cur[0]\n",
    "                while temp < len(maze) and maze[temp][cur[1]] == 0:\n",
    "                    temp +=1\n",
    "                temp -= 1\n",
    "                if (temp* width + cur[1])  not in visited:\n",
    "                    # visited.append(cur_)\n",
    "                    que.append([temp, cur[1]])\n",
    "                stop.append([temp,cur[1]])\n",
    "            que.pop(0)\n",
    "        \n",
    "        return destination in stop\n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "#         stop = []\n",
    "#         que = []\n",
    "#         que.append(start)\n",
    "#         while que:\n",
    "#             cur = que[0]\n",
    "#             if maze[cur[0]][cur[1]] == 2:\n",
    "#                 que.pop(0)\n",
    "#                 continue\n",
    "            \n",
    "#             countWall = 0\n",
    "#             wall = []\n",
    "#             for i in [[0,-1],[0,1],[-1,0],[1,0]]:\n",
    "#                 nextRow = cur[0] + i[0]\n",
    "#                 nextCol = cur[1] + i[1]\n",
    "#                 if 0<=nextRow<len(maze) and 0<=nextCol<len(maze[0]):\n",
    "#                     wall.append(maze[nextRow][nextCol])\n",
    "#                     if maze[nextRow][nextCol] == 1:\n",
    "#                         countWall += 1\n",
    " \n",
    "#                         continue\n",
    "#                     elif maze[nextRow][nextCol] == 0:\n",
    "#                         que.append([nextRow,nextCol])\n",
    "#                 else:\n",
    "#                     wall.append(1)\n",
    "#                     countWall += 1\n",
    "            \n",
    "            \n",
    "#             if countWall == 3:\n",
    "#                 stop.append([cur[0],cur[1]])\n",
    "#             elif countWall == 2:\n",
    "#                 if (wall[0] == 1 and wall[2] == 1) or(wall[0] == 1 and wall[3]==1):\n",
    "#                     stop.append([cur[0],cur[1]])\n",
    "#                 elif(wall[1] == 1 and wall[2] == 1) or(wall[1] == 1 and wall[3]==1):\n",
    "#                     stop.append([cur[0],cur[1]])\n",
    "                    \n",
    "                    \n",
    "#             maze[cur[0]][cur[1]] = 2 \n",
    "            \n",
    "#             que.pop(0)\n",
    "        \n",
    "#         return destination in stop\n",
    "                        \n",
    "                        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def move(self, maze, position, x, y):\n",
    "        # 向左移动\n",
    "        if position == [0, -1]:\n",
    "            while(y - 1 >= 0)and (maze[x][y-1] != 1):\n",
    "                y -= 1\n",
    "        # 向右移动\n",
    "        elif position == [0, 1]:\n",
    "            while(y + 1 <= self.cols - 1) and (maze[x][y+1] != 1):\n",
    "                y += 1\n",
    "        # 向上移动\n",
    "        elif position == [-1, 0]:\n",
    "            while (x - 1 >= 0) and (maze[x-1][y] != 1):\n",
    "                x -= 1\n",
    "        # 向下移动\n",
    "        elif position == [1, 0]:\n",
    "            while (x + 1 <= self.rows - 1) and (maze[x+1][y] != 1):\n",
    "                x += 1\n",
    "\n",
    "        return x, y\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        #          [x-1, y]\n",
    "        # [x, y-1] [x, y] [x, y+1]\n",
    "        #          [x+1, y]\n",
    "        self.positions = [[0, -1], [-1, 0], [0, 1], [1, 0]]\n",
    "        self.rows = len(maze)\n",
    "        self.cols = len(maze[0])\n",
    "        # 表示当前单元格是否被访问过\n",
    "        visit = [[False] * self.cols for row in range(self.rows)]\n",
    "        return self.bfs(maze, visit, start[0], start[1], destination)\n",
    "\n",
    "    def bfs(self, maze, visit, x, y, destination):\n",
    "        queue = deque()\n",
    "        queue.append((x, y))\n",
    "        visit[x][y] = True\n",
    "        # 假设无法到达迷宫终点\n",
    "        tag = False\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            if x == destination[0] and y == destination[1]:\n",
    "                tag = True\n",
    "                break\n",
    "            for position in self.positions:\n",
    "                x_new, y_new = self.move(maze, position, x, y)\n",
    "                if not visit[x_new][y_new]:\n",
    "                    queue.append((x_new, y_new))\n",
    "                    visit[x_new][y_new] = True\n",
    "\n",
    "        return tag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        row, col = len(maze), len(maze[0])\n",
    "        visited = set()\n",
    "        stack = [(start[0],start[1])]\n",
    "        while stack:\n",
    "            i,j = stack.pop()\n",
    "            if [i, j] == destination:\n",
    "                return True\n",
    "            visited.add((i, j))\n",
    "            for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                tmp_i = i\n",
    "                tmp_j = j\n",
    "                while 0 <= tmp_i + x < row and 0 <= tmp_j + y < col and maze[tmp_i + x][tmp_j + y] == 0:\n",
    "                    tmp_i += x\n",
    "                    tmp_j += y\n",
    "                if tmp_i == i and tmp_j == j:\n",
    "                    continue\n",
    "                if (tmp_i, tmp_j) not in visited:\n",
    "                    stack.append((tmp_i, tmp_j))\n",
    "        return False\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "\n",
    "        \"\"\"try depth\"\"\"\n",
    "        #initialie the beginning position\n",
    "        row = len(maze)\n",
    "        col = len(maze[0])\n",
    "        queue = []\n",
    "        queue.append(start)\n",
    "        maze[start[0]][start[1]] = -1\n",
    "\n",
    "        directions = [[0,1],[0,-1],[1,0], [-1,0]]\n",
    "        \n",
    "        while queue:\n",
    "            top = queue.pop(0)\n",
    "            if top == destination:\n",
    "                return True\n",
    "\n",
    "            # make decision on next direction\n",
    "            for di, dj in directions:\n",
    "                i,j = top[0], top[1]\n",
    "                # next postion should not be visited and should be in maze(in range)\n",
    "                # ball cannot stop before hit the wall(and keep the same direction)\n",
    "                while 0 <= i+di < row and 0<= j+dj < col and (maze[i+di][j+dj] == 0 or maze[i+di][j+dj] == -1):\n",
    "                    i = i + di\n",
    "                    j = j + dj\n",
    "    #             print(\"check\", [i, j])\n",
    "                \n",
    "                if maze[i][j] != -1:\n",
    "                    maze[i][j] = -1   \n",
    "                    queue.append([i,j])\n",
    "    #             print(queue)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        q = [start]\n",
    "        visited = [[False]*n for i in range(m)]\n",
    "        while q:\n",
    "            st = q.pop()\n",
    "            x = st[0]\n",
    "            y = st[1]\n",
    "            for dir_tmp in dirs:\n",
    "                x_new = x + dir_tmp[0]\n",
    "                y_new = y + dir_tmp[1]\n",
    "                while 0 <= x_new < m and 0 <= y_new < n and maze[x_new][y_new] == 0:\n",
    "                    x_new += dir_tmp[0]\n",
    "                    y_new += dir_tmp[1]\n",
    "                x_new -= dir_tmp[0]\n",
    "                y_new -= dir_tmp[1]\n",
    "                if x_new == destination[0] and y_new == destination[1]:\n",
    "                    return True\n",
    "                if 0 <= x_new < m and 0 <= y_new < n and maze[x_new][y_new] == 0 and not visited[x_new][y_new]:\n",
    "                    visited[x_new][y_new] = True\n",
    "                    q.append([x_new, y_new])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        directions = [(0,1),(1,0),(-1,0),(0,-1)]    # 定义上下左右四个方向\n",
    "        m = len(maze)                               # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "\n",
    "        queue = [(start[0],start[1])]               # 构造队列，并将起始位置包含其中\n",
    "        maze[start[0]][start[1]] = -1               # -1表示该点已经过遍历，防止循环\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)                      # 弹出坐标值i,j\n",
    "                                                    # 如果坐标为终点坐标，返回True，程序结束\n",
    "            if i == destination[0] and j == destination[1]:\n",
    "                return True\n",
    "            for dx,dy in directions:                # 对四个方向进行遍历\n",
    "                x,y =i,j\n",
    "                while 0<=x+dx<m and 0<=y+dy<n and (maze[x+dx][y+dy] == 0 or maze[x+dx][y+dy]==-1):                                      \n",
    "                                                    # 当x,y坐标合法，并且对应值为0或-1时\n",
    "                    x = x+dx                        # 继续前进，模拟小球的滚动过程\n",
    "                    y = y+dy                        # 其中0为空地，而-1为之前遍历过的空地\n",
    "                if maze[x][y]!=-1:                  # 如果该点的值不为-1，即未遍历过\n",
    "                    maze[x][y] = -1                 # 置为1\n",
    "                    queue.append((x,y))             # 并将其坐标添加到队列中\n",
    "            \n",
    "                                                    # 如果遍历所有可能性都无法达到目的地\n",
    "        return False             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        if not maze:\n",
    "            return False\n",
    "        queue = collections.deque()\n",
    "        queue.append(start)\n",
    "\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            if x == destination[0] and y==destination[1]:\n",
    "                return True\n",
    "            \n",
    "            maze[x][y] = 2\n",
    "            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):\n",
    "                row,col = self.move(x,y,dx,dy,maze)\n",
    "                if maze[row][col] == 0:\n",
    "                    queue.append([row,col])\n",
    "        \n",
    "        return False\n",
    "    def move(self,x,y,dx,dy,maze):\n",
    "        while 0 <= x < len(maze) and 0<= y < len(maze[0]) and maze[x][y]!=1:\n",
    "            x+=dx\n",
    "            y+=dy\n",
    "        return x-dx,y-dy\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        row = len(maze)\n",
    "        col = len(maze[0])\n",
    "        delta_list = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        if not start:\n",
    "            return False\n",
    "        q = deque([start])\n",
    "        visited_p = set()\n",
    "        visited_p.add((start[0], start[1]))\n",
    "        while q:\n",
    "            cur_point = q.popleft()\n",
    "            if cur_point == destination:\n",
    "                return True\n",
    "            for temp_list in delta_list:\n",
    "                x = cur_point[0]\n",
    "                y = cur_point[1]\n",
    "                dx = temp_list[0]\n",
    "                dy = temp_list[1]\n",
    "                while x+dx>=0 and x+dx<row and y+dy>=0 and y+dy<col and maze[x+dx][y+dy] == 0:\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                if (x, y) not in visited_p:\n",
    "                    visited_p.add((x, y))\n",
    "                    q.append([x, y])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maze = []\n",
    "\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        self.maze = maze\n",
    "\n",
    "        start, destination = tuple(start), tuple(destination)\n",
    "\n",
    "        visited = {start}\n",
    "        queue = collections.deque([start])\n",
    "        while queue:\n",
    "            print(queue)\n",
    "            now = queue.popleft()\n",
    "            for next in self.move(now):\n",
    "                if next == destination:\n",
    "                    return True\n",
    "                if next not in visited:\n",
    "                    queue.append(next)\n",
    "                    visited.add(next)\n",
    "\n",
    "        return False\n",
    "\n",
    "    def move(self, start):\n",
    "        res = []\n",
    "\n",
    "        # 向上移动\n",
    "        v1 = start[0]\n",
    "        for i in range(start[0] - 1, -1, -1):\n",
    "            if self.maze[i][start[1]] == 0:\n",
    "                v1 = i\n",
    "            else:\n",
    "                break\n",
    "        if v1 != start[0]:\n",
    "            res.append((v1, start[1]))\n",
    "\n",
    "        # 向下移动\n",
    "        v2 = start[0]\n",
    "        for i in range(start[0] + 1, len(self.maze), 1):\n",
    "            if self.maze[i][start[1]] == 0:\n",
    "                v2 = i\n",
    "            else:\n",
    "                break\n",
    "        if v2 != start[0]:\n",
    "            res.append((v2, start[1]))\n",
    "\n",
    "        # 向左移动\n",
    "        v3 = start[1]\n",
    "        for j in range(start[1] - 1, -1, -1):\n",
    "            if self.maze[start[0]][j] == 0:\n",
    "                v3 = j\n",
    "            else:\n",
    "                break\n",
    "        if v3 != start[1]:\n",
    "            res.append((start[0], v3))\n",
    "\n",
    "        # 向右移动\n",
    "        v4 = start[1]\n",
    "        for j in range(start[1] + 1, len(self.maze[0]), 1):\n",
    "            if self.maze[start[0]][j] == 0:\n",
    "                v4 = j\n",
    "            else:\n",
    "                break\n",
    "        if v4 != start[1]:\n",
    "            res.append((start[0], v4))\n",
    "\n",
    "        # print(\"MOVE:\", start, \"->\", res, \"(\", v1, v2, v3, v4, \")\")\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, x, y):\n",
    "        if x == self.destination[0] and \\\n",
    "           y == self.destination[1]: \n",
    "           # print(\"True\")\n",
    "           return True\n",
    "        if self.maze[x][y] == 1: return False\n",
    "        self.maze[x][y] = -1 # -1 represents visited\n",
    "        for d in self.dir:\n",
    "            dx = x + d[0]\n",
    "            dy = y + d[1]\n",
    "            while 0 <= dx < self.m and 0 <= dy < self.n and self.maze[dx][dy] != 1:\n",
    "                dx += d[0]\n",
    "                dy += d[1]\n",
    "            dx -= d[0]\n",
    "            dy -= d[1]\n",
    "            if 0 <= dx < self.m and 0 <= dy < self.n and self.maze[dx][dy] != -1:\n",
    "                if self.dfs(dx, dy): return True\n",
    "\n",
    "        # self.maze[x][y] = 0\n",
    "        return False\n",
    "\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        self.maze = maze\n",
    "        self.m = len(maze)\n",
    "\n",
    "        if self.m == 0: return False\n",
    "        self.n = len(maze[0])\n",
    "        self.destination = destination\n",
    "        self.dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        return self.dfs(start[0], start[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        directions = [(0,1),(1,0),(-1,0),(0,-1)]    \n",
    "        m = len(maze)                              \n",
    "        n = len(maze[0])                                                  \n",
    "        def dfs(m,n,maze,x,y,directions,destination):\n",
    "            maze[x][y] = -1                                                                           \n",
    "            if x==destination[0] and y==destination[1]:\n",
    "                return True           \n",
    "            res = False\n",
    "            i,j = x,y                               \n",
    "            for dx,dy in directions:               \n",
    "                x,y =i,j\n",
    "                while 0<=x+dx<m and 0<=y+dy<n and (maze[x+dx][y+dy] == 0 or maze[x+dx][y+dy]==-1):             \n",
    "                    x = x+dx                       \n",
    "                    y = y+dy                        \n",
    "                if maze[x][y]!=-1:                                                                     \n",
    "                    res = res or dfs(m, n, maze, x, y, directions, destination)\n",
    "            return res                              \n",
    "        return dfs(m, n, maze, start[0], start[1], directions, destination)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        sx, sy = start\n",
    "        ex, ey = destination\n",
    "        que = deque([[sx, sy]])\n",
    "        vis = [[0] * n for _ in range(m)]; vis[sx][sy] = 1\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        while que:\n",
    "            curx, cury = que.popleft()\n",
    "            # print(curx, cury)\n",
    "            if curx == ex and cury == ey:\n",
    "                return True\n",
    "            for i in range(4):\n",
    "                nxtx, nxty = curx, cury\n",
    "                while 0 <= nxtx + dirs[i][0] < m and 0 <= nxty + dirs[i][1] < n and maze[nxtx + dirs[i][0]][nxty + dirs[i][1]] == 0:\n",
    "                    nxtx += dirs[i][0]; nxty += dirs[i][1]\n",
    "                if vis[nxtx][nxty] == 0:\n",
    "                    que.append([nxtx, nxty])\n",
    "                    vis[nxtx][nxty] = 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        return self.bfs(maze, start, destination)\n",
    "\n",
    "    def bfs(self, maze, start, destination):\n",
    "        Row, Col = len(maze), len(maze[0])\n",
    "        visited = [[False] * Col for _ in range(Row)]\n",
    "        Q = [(start[0], start[1])]\n",
    "        visited[start[0]][start[1]] = True\n",
    "        while Q:\n",
    "            r, c = Q.pop(0)\n",
    "            if [r, c] == destination:\n",
    "                return True\n",
    "            for dr, dc in ((0,1),(1,0),(0,-1),(-1,0)):\n",
    "                nr = r + dr\n",
    "                nc = c + dc\n",
    "                while 0 <= nr < Row and 0 <= nc < Col and maze[nr][nc] == 0:\n",
    "                    nr += dr\n",
    "                    nc += dc\n",
    "                nr -= dr\n",
    "                nc -= dc\n",
    "                if visited[nr][nc] == False:\n",
    "                    visited[nr][nc] = True\n",
    "                    Q.append((nr, nc))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        q = deque([start])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        vis[start[0]][start[1]] = True\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            if [x, y] == destination:\n",
    "                return True\n",
    "            \n",
    "            for dx, dy in dirs:\n",
    "                # 为什么这里一定要用nx, ny? \n",
    "                # 因为如果不用的话, 在遍历dirs 的下一个方向的时候, x 和 y 的位置不是起点的位置了\n",
    "                nx, ny = x, y\n",
    "                while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:\n",
    "                    nx += dx \n",
    "                    ny += dy\n",
    "                if not vis[nx][ny]:\n",
    "                    vis[nx][ny] = True\n",
    "                    q.append((nx, ny))\n",
    "        \n",
    "        return False\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        n, m = len(maze), len(maze[0])\n",
    "        directions = [(0,1), (0, -1), (1, 0), (-1, 0)]\n",
    "        visited = [[False for j in range(m)] for i in range(n)]\n",
    "\n",
    "        # def dfs(x, y):\n",
    "        #     if visited[x][y]:\n",
    "        #         return False\n",
    "        #     if (x, y) == destination:\n",
    "        #         return True\n",
    "            \n",
    "        #     visited[x][y] = 1\n",
    "\n",
    "        #     u = x - 1\n",
    "        #     d = x + 1\n",
    "        #     l = y - 1\n",
    "        #     r = y + 1\n",
    "\n",
    "        #     while u >= 0 and maze[u][y] == 0:\n",
    "        #         u -= 1\n",
    "        #     if dfs(u + 1, y):\n",
    "        #         return True\n",
    "        #     while d < n and maze[d][y] == 0:\n",
    "        #         d += 1\n",
    "        #     if dfs(d - 1, y):\n",
    "        #         return True\n",
    "        #     while l >= 0 and maze[x][l] == 0:\n",
    "        #         l -=1\n",
    "        #     if dfs(x, l + 1):\n",
    "        #         return True\n",
    "        #     while r < m and maze[x][r] == 0:\n",
    "        #         r += 1\n",
    "        #     if dfs(x, r - 1):\n",
    "        #         return True\n",
    "        #     return False\n",
    "        \n",
    "        # return dfs(start[0], start[1])\n",
    "\n",
    "\n",
    "        que = collections.deque()\n",
    "        que.append((start[0], start[1]))\n",
    "        visited[start[0]][start[1]] = True\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            if [x, y] == destination:\n",
    "                return True\n",
    "            \n",
    "            for i , j in directions:\n",
    "                sx = x + i\n",
    "                sy = y + j\n",
    "\n",
    "                while sx >= 0 and sy >= 0 and sx < n and sy < m and maze[sx][sy] == 0:\n",
    "                    sx += i\n",
    "                    sy += j\n",
    "\n",
    "                if not visited[sx - i][sy - j]:\n",
    "                    que.append((sx - i, sy - j))\n",
    "                    visited[sx - i][sy - j] = True\n",
    "        return False \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "\n",
    "        ROW, COL = len(maze), len(maze[0])\n",
    "        q = deque([(start[0], start[1])])\n",
    "        visited = set([(start[0], start[1])])\n",
    "        \n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                row, col = q.popleft()\n",
    "                if row == destination[0] and col == destination[1]:\n",
    "                    return True\n",
    "                    \n",
    "                for dr, dc in [[-1, 0], [0, 1], [1, 0], [0, -1]]:\n",
    "                    r, c = row + dr, col + dc\n",
    "                    while 0 <= r < ROW and 0 <= c < COL and maze[r][c] == 0:\n",
    "                        r, c = r + dr, c + dc\n",
    "                    r, c = r - dr, c - dc\n",
    "\n",
    "                    if (r, c) not in visited:\n",
    "                        q.append((r, c))\n",
    "                        visited.add((r, c))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        #图的遍历 -> BFS/Dijstra\n",
    "        direction = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        #球往一个方向动，碰到墙壁或者边界才会停下来\n",
    "        visited = set()\n",
    "        q = [start]\n",
    "        while q:\n",
    "            pos = q.pop(0)\n",
    "            print(pos)\n",
    "            if pos==destination: return True\n",
    "            if tuple(pos) in visited: continue\n",
    "            visited.add(tuple(pos))\n",
    "            \n",
    "            for di, dj in direction:\n",
    "                i, j = pos\n",
    "                while True:\n",
    "                    if i+di<0 or j+dj<0 or i+di==m or j+dj==n or maze[i+di][j+dj]==1:\n",
    "                        break\n",
    "                    i, j = i+di, j+dj \n",
    "                print('new pos', i, j)\n",
    "                q.append([i,j])\n",
    "        return False\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        directions=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        queue=[(start[0],start[1])]\n",
    "        maze[start[0]][start[1]]=-1\n",
    "\n",
    "        while queue:\n",
    "            i,j=queue.pop(0)\n",
    "            if i==destination[0] and j==destination[1]:\n",
    "                return True\n",
    "            for dx,dy in directions:\n",
    "                x,y=i,j\n",
    "                while 0<=x+dx<m and 0<=y+dy<n and (maze[x+dx][y+dy]==0 or maze[x+dx][y+dy]==-1):\n",
    "                    x=x+dx\n",
    "                    y=y+dy\n",
    "                if maze[x][y]!=-1:\n",
    "                    maze[x][y]=-1\n",
    "                    queue.append((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        directions=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        # -1 represt visited\n",
    "        maze[start[0]][start[1]]=-1\n",
    "        queue=[(start[0],start[1])]\n",
    "\n",
    "        while queue:\n",
    "            i,j=queue.pop(0)\n",
    "            if i==destination[0] and j==destination[1]:\n",
    "                return True\n",
    "            for dx,dy in directions:\n",
    "                x,y=i,j\n",
    "                while 0<=x+dx<m and 0<=y+dy<n and (maze[x+dx][y+dy]==0 or maze[x+dx][y+dy]==-1):\n",
    "                    x+=dx\n",
    "                    y+=dy\n",
    "                if maze[x][y]!=-1:\n",
    "                    maze[x][y]=-1\n",
    "                    queue.append((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        quene=deque()\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        quene.append(start)\n",
    "        vis=set()\n",
    "        destination=tuple(destination)\n",
    "        vis.add(tuple(start))\n",
    "        while quene:\n",
    "            pos=quene.popleft()\n",
    "            if pos==destination:\n",
    "                return True\n",
    "            x,y=pos[0],pos[1]\n",
    "            #向上\n",
    "            while x>=0 and maze[x][y]==0:\n",
    "                x-=1\n",
    "            x+=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "            #向下\n",
    "            x,y=pos[0],pos[1]\n",
    "            while x<m and maze[x][y]==0:\n",
    "                x+=1\n",
    "            x-=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "            #向左\n",
    "            x,y=pos[0],pos[1]\n",
    "            while y>=0 and maze[x][y]==0:\n",
    "                y-=1\n",
    "            y+=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "            #向右\n",
    "            x,y=pos[0],pos[1]\n",
    "            while y<n and maze[x][y]==0:\n",
    "                y+=1\n",
    "            y-=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        quene=deque()\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        quene.append(start)\n",
    "        vis=set()\n",
    "        destination=tuple(destination)\n",
    "        vis.add(tuple(start))\n",
    "        while quene:\n",
    "            pos=quene.popleft()\n",
    "            if pos==destination:\n",
    "                return True\n",
    "            x,y=pos[0],pos[1]\n",
    "            #向上\n",
    "            while x>=0 and maze[x][y]==0:\n",
    "                x-=1\n",
    "            x+=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "            #向下\n",
    "            x,y=pos[0],pos[1]\n",
    "            while x<m and maze[x][y]==0:\n",
    "                x+=1\n",
    "            x-=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "            #向左\n",
    "            x,y=pos[0],pos[1]\n",
    "            while y>=0 and maze[x][y]==0:\n",
    "                y-=1\n",
    "            y+=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "            #向右\n",
    "            x,y=pos[0],pos[1]\n",
    "            while y<n and maze[x][y]==0:\n",
    "                y+=1\n",
    "            y-=1\n",
    "            if (x,y) not in vis:\n",
    "                quene.append((x,y))\n",
    "                vis.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        v = []\n",
    "        maze_2 = [[1]*(len(maze[0]) + 2) for _ in range(len(maze) + 2)]\n",
    "        for i in range(1, len(maze_2) - 1):\n",
    "            for j in range(1, len(maze_2[0]) - 1):\n",
    "                if maze[i - 1][j - 1] == 0:\n",
    "                    maze_2[i][j] = 0\n",
    "                    v.append([i, j])\n",
    "        \n",
    "        s_r, s_c = start[0] + 1, start[1] + 1\n",
    "        e_r, e_l = destination[0] + 1, destination[1] + 1\n",
    "\n",
    "        dq = deque()\n",
    "        dq.append([s_r, s_c])\n",
    "        while dq:\n",
    "            if [e_r, e_l] in dq:\n",
    "                return True\n",
    "            for i in range(len(dq)):\n",
    "                x, y = dq.popleft()\n",
    "                a, b = x, y\n",
    "                while maze_2[x][y] == 0:\n",
    "                    x -= 1\n",
    "                x += 1\n",
    "                if [x, y] in v:\n",
    "                    dq.append([x, y])\n",
    "                    v.remove([x, y]) \n",
    "\n",
    "                x, y = a, b\n",
    "                while maze_2[x][y] == 0:\n",
    "                    y -= 1\n",
    "                y += 1\n",
    "                if [x, y] in v:\n",
    "                    dq.append([x, y])\n",
    "                    v.remove([x, y]) \n",
    "\n",
    "                x, y = a, b\n",
    "                while maze_2[x][y] == 0:\n",
    "                    x += 1\n",
    "                x -= 1\n",
    "                if [x, y] in v:\n",
    "                    dq.append([x, y])\n",
    "                    v.remove([x, y]) \n",
    "\n",
    "                x, y = a, b\n",
    "                while maze_2[x][y] == 0:\n",
    "                    y += 1\n",
    "                y -= 1\n",
    "                if [x, y] in v:\n",
    "                    dq.append([x, y])\n",
    "                    v.remove([x, y]) \n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        vis=set()\n",
    "        dirs=[[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        q=[]\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        for i in range(4):\n",
    "            q.append((start[0],start[1],i))\n",
    "            vis.add((start[0],start[1],i))\n",
    "        while q:\n",
    "            x,y,d=q.pop()\n",
    "            while 0<=x+dirs[d][0]<m and 0<=y+dirs[d][1]<n and maze[x+dirs[d][0]][y+dirs[d][1]]==0:\n",
    "                x,y=x+dirs[d][0],y+dirs[d][1]\n",
    "            if x==destination[0] and y==destination[1]:\n",
    "                return True\n",
    "            for i in range(4):\n",
    "                if i!=d and (x,y,i) not in vis:\n",
    "                    vis.add((x,y,i))\n",
    "                    q.append((x,y,i))\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "\n",
    "        end_point = {}\n",
    "\n",
    "        # 找到 从 (i, j) 能到达的 全部 end_point\n",
    "        def find_end(i, j):\n",
    "\n",
    "            \n",
    "            if (i, j) in end_point:\n",
    "                return end_point[(i, j)]\n",
    "            end_point[(i, j)] = []\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                a, b = i, j\n",
    "                da = a + dx\n",
    "                db = b + dy\n",
    "                while da > -1 and da < m and db > -1 and db < n and maze[da][db] == 0:\n",
    "                    a, b = da, db\n",
    "                    da = a + dx\n",
    "                    db = b + dy\n",
    "                if a == i and b == j:\n",
    "                    continue\n",
    "                end_point[(i, j)].append((a, b))\n",
    "            return end_point[(i, j)] \n",
    "        \n",
    "        queue = deque([(start[0], start[1])])\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                i, j = queue.popleft()\n",
    "                if (i, j) in end_point:\n",
    "                    continue\n",
    "                neighbors = find_end(i, j)\n",
    "                for neighbor in neighbors:\n",
    "                    if neighbor[0] == destination[0] and neighbor[1] == destination[1]:\n",
    "                        return True\n",
    "                    queue.append(neighbor)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "\n",
    "        end_point = {}\n",
    "\n",
    "        # 找到 从 (i, j) 能到达的 全部 end_point\n",
    "        def find_end(i, j):\n",
    "\n",
    "            \n",
    "            if (i, j) in end_point:\n",
    "                return end_point[(i, j)]\n",
    "            end_point[(i, j)] = []\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                a, b = i, j\n",
    "                da = a + dx\n",
    "                db = b + dy\n",
    "                while da > -1 and da < m and db > -1 and db < n and maze[da][db] == 0:\n",
    "                    a, b = da, db\n",
    "                    da = a + dx\n",
    "                    db = b + dy\n",
    "                if a == i and b == j:\n",
    "                    continue\n",
    "                end_point[(i, j)].append((a, b))\n",
    "            return end_point[(i, j)] \n",
    "        \n",
    "        queue = deque([(start[0], start[1])])\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                i, j = queue.popleft()\n",
    "                if (i, j) in end_point:\n",
    "                    continue\n",
    "                neighbors = find_end(i, j)\n",
    "                for neighbor in neighbors:\n",
    "                    if neighbor[0] == destination[0] and neighbor[1] == destination[1]:\n",
    "                        return True\n",
    "                    queue.append(neighbor)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        dirs = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        self.v = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def bfs(x, y):\n",
    "            if x == destination[0] and y == destination[1]:\n",
    "                return True\n",
    "                \n",
    "            self.v[x][y] = True\n",
    "\n",
    "            for dir in dirs:\n",
    "                x1, y1 = x + dir[0], y + dir[1]\n",
    "                while not (x1 < 0 or y1 < 0 or x1 >= m or y1 >= n) and maze[x1][y1] == 0:\n",
    "                    x1, y1 = x1 + dir[0], y1 + dir[1]\n",
    "                \n",
    "                if self.v[x1 - dir[0]][y1 - dir[1]]:\n",
    "                    continue\n",
    "\n",
    "                if bfs(x1 - dir[0], y1 - dir[1]):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return bfs(start[0], start[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        visited = set()\n",
    "        dirs = ((-1,0),(0,1),(1,0),(0,-1))\n",
    "        ans = [False]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if ans[0]: return\n",
    "            if i == destination[0] and j == destination[1]:\n",
    "                ans[0] = True\n",
    "                return\n",
    "            if (i,j) in visited: return\n",
    "            visited.add((i,j))\n",
    "            for d in dirs:\n",
    "                ni, nj = i, j\n",
    "                while 0<=ni+d[0]<len(maze) and 0<=nj+d[1]<len(maze[0]) and maze[ni+d[0]][nj+d[1]]!=1:\n",
    "                    ni += d[0]\n",
    "                    nj += d[1]\n",
    "                dfs(ni, nj)\n",
    "        \n",
    "        dfs(start[0], start[1])\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        rds=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        startx,starty=start\n",
    "        desx,dexy=destination\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        visited=set()\n",
    "        def getNx(x,y,rx,ry):\n",
    "            while(0<=x+rx<m and 0<=y+ry<n and maze[x+rx][y+ry]==0):\n",
    "                x=x+rx\n",
    "                y=y+ry\n",
    "            return (x,y)\n",
    "        def dfs(x,y):\n",
    "            if x==desx and y==dexy:\n",
    "                return True\n",
    "            for rx,ry in rds:\n",
    "                nx,ny=getNx(x,y,rx,ry)    \n",
    "                if (nx,ny) not in visited:\n",
    "                    visited.add((nx,ny))\n",
    "                    if dfs(nx,ny):\n",
    "                        return True\n",
    "            return False\n",
    "        visited.add((startx,starty))\n",
    "        return dfs(startx,starty)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        rds=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        startx,starty=start\n",
    "        desx,dexy=destination\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        visited=set()\n",
    "        # @cache\n",
    "        def getNx(x,y,rx,ry):\n",
    "            while(0<=x+rx<m and 0<=y+ry<n and maze[x+rx][y+ry]==0):\n",
    "                x=x+rx\n",
    "                y=y+ry\n",
    "            return (x,y)\n",
    "\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            if x==desx and y==dexy:\n",
    "                return True\n",
    "            for rx,ry in rds:\n",
    "                nx,ny=getNx(x,y,rx,ry)    \n",
    "                if (nx,ny) not in visited:\n",
    "                    visited.add((nx,ny))\n",
    "                    if dfs(nx,ny):\n",
    "                        return True\n",
    "            return False\n",
    "        visited.add((startx,starty))\n",
    "        return dfs(startx,starty)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:\n",
    "        visited = set()\n",
    "        dirs = ((-1,0),(0,1),(1,0),(0,-1))\n",
    "        ans = [False]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if ans[0]: return\n",
    "            if i == destination[0] and j == destination[1]:\n",
    "                ans[0] = True\n",
    "                return\n",
    "            if (i,j) in visited: return\n",
    "            visited.add((i,j))\n",
    "            for d in dirs:\n",
    "                ni, nj = i, j\n",
    "                while 0<=ni+d[0]<len(maze) and 0<=nj+d[1]<len(maze[0]) and maze[ni+d[0]][nj+d[1]]!=1:\n",
    "                    ni += d[0]\n",
    "                    nj += d[1]\n",
    "                dfs(ni, nj)\n",
    "        \n",
    "        dfs(start[0], start[1])\n",
    "        return ans[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
